﻿#include <iostream>
#include <algorithm>

using namespace std;

#define MIN(a,b) (a<b?a:b)

static void swap(int* arr, const int index1, const int index2)
{
	if (index1 == index2) return;

	arr[index1] = arr[index1] ^ arr[index2];
	arr[index2] = arr[index1] ^ arr[index2];
	arr[index1] = arr[index1] ^ arr[index2];
}

static int* partition(int* arr, const size_t arrSize, const int begin, const int end, const int pivotValue)
{
	int small = begin - 1;
	int cur = begin;
	int big = end + 1;
	while (cur != big)
	{
		if (arr[cur] < pivotValue)
		{
			swap(arr, ++small, cur++);
		}
		else if (arr[cur] > pivotValue)
		{
			swap(arr, cur, --big);
		}
		else
		{
			++cur;
		}
	}

	int* range = (int*)malloc(2 * sizeof(int));
	range[0] = small + 1;
	range[1] = big - 1;
	return range;
}

static int medianOfMedians(int* arr, const size_t arrSize, const int begin, const int end);

/**
 * 在arr[begin..end]范围上，求如果排序的话，i位置的数字是哪个，返回。
 * i一定在begin~end范围上
 */
static int select(int* arr, const size_t arrSize, const int begin, const int end, const int i)
{
	if (begin == end)
	{
		return arr[begin];
	}

	if (end - begin == 1)
	{
		if (arr[begin] > arr[end])
		{
			swap(arr, begin, end);
		}

		return arr[i];
	}

	// 分组+组内排序+组成newarr+选出newarr的上中位数pivot
	int pivot = medianOfMedians(arr, arrSize, begin, end);
	// 根据pivot做划分值，<p ==p >p, 返回等于区域的左边界和右边界
	// pivotRange[0] 等于区域的左边界
	// pivotRange[1] 等于区域的右边界
	int* pivotRange = partition(arr, arrSize, begin, end, pivot);
	int pivotRange0 = pivotRange[0];
	int pivotRange1 = pivotRange[1];
	free(pivotRange);

	if (i > pivotRange0 && i <= pivotRange1)
	{
		return arr[i];
	}
	else if (i < pivotRange0)
	{
		return select(arr, arrSize, begin, pivotRange0 - 1, i);
	}
	else
	{
		return select(arr, arrSize, pivotRange1 + 1, end, i);
	}
}

static int getMedian(int* arr, const size_t arrSize, int begin, const int end)
{
	sort(arr + begin, arr + end + 1, less<int>());
	int sum = end + begin;
	int mid = (sum / 2) + (sum % 2);
	return arr[mid];
}

static int medianOfMedians(int* arr, const size_t arrSize, const int begin, const int end)
{
	int num = end - begin + 1;
	int offset = num % 5 == 0 ? 0 : 1;
	int mArrSize = num / 5 + offset;
	int* mArr = (int*)malloc(mArrSize * sizeof(int));
	memset(mArr, 0, mArrSize * sizeof(int));
	for (int i = 0; i < mArrSize; i++)
	{
		int beginI = begin + i * 5;
		int endI = beginI + 4;
		int min = MIN(end, endI);
		mArr[i] = getMedian(arr, arrSize, beginI, min);
	}

	int res = select(mArr, mArrSize, 0, mArrSize - 1, mArrSize / 2);
	free(mArr);
	return res;
}

static int* copyArray(const int* arr, const size_t arrSize)
{
	int* res = (int*)malloc(arrSize * sizeof(int));
	memcpy_s(res, arrSize * sizeof(int), arr, arrSize * sizeof(int));
	return res;
}

static int getMinKthByBFPRT(const int* arr, const size_t arrSize, const int K)
{
	int* copyArr = copyArray(arr, arrSize);
	int res = select(copyArr, arrSize, 0, arrSize - 1, K - 1);
	free(copyArr);
	return res;
}

static int* getMinKNumsByBFPRT(int* arr, const size_t arrSize, const int k)
{
	if (k < 1 || k > arrSize) 
	{
		return arr;
	}

	int minKth = getMinKthByBFPRT(arr, arrSize, k);
	int* res = (int*)malloc(k * sizeof(int));
	memset(res, 0, k * sizeof(int));
	int index = 0;
	for (int i = 0; i < arrSize; i++)
	{
		if (arr[i] < minKth)
		{
			res[index++] = arr[i];
		}
	}

	int resSize = k;
	for (;index < resSize; index++)
	{
		res[index] = minKth;
	}

	return res;
}

/**
 * 在一个无序数组中，求最小的第k个数
 * 
 * 思路：
 * 常规方法：
 * 1. 随机选取一个数字n，以它进行partition操作，将数组分成<n,==n,<n的三部分
   2. 看第k个数字在哪个范围，如果刚好在==n的范围，直接返回n；如果在>n或者<n的范围，则定位到这一部分，递归执行之前的操作，直到找到==选取的随机数字的部分返回

   常规方法的缺点在于时间复杂度依赖于给的样本的情况，O(N)~O(N^2)

   BFPRT算法:
   1. 使用特殊方法选择一个数字n，将数组分成<n,==n,<n的三部分
   2. 看第k个数字在哪个范围，如果刚好在==n的范围，直接返回n；如果在>n或者<n的范围，则定位到这一部分，递归执行之前的操作，直到找到==选取的数字的部分返回

   BFPRT算法与常规方法唯一的区别在于选择进行partition的数字上，BFPRT算法的时间复杂度是严格的O(N)
   设算法的函数是f(arr, k)
   1. 将arr从左到右，五个数字分成一个组。 0~4,5~9，10~14,15~19，... 倘若最后一组不够五个数字，则有多少算多少构成最后的一组。
   2. 每组中取出中位数，组成一个新的数组marr, [a,b,c,d,...]. 如果最后一组的数字是偶数个，则取上中位数
   3. 求marr的中位数，marr是偶数个，则取上中位数。如何求？递归调用f(marr, marr.Length/2), 它的返回值作为选中的数字，然后进行和常规方法同样的partition流程。

 */
int main_theKthSmallNumber()
{
	int arr[] = {1,5,4,3,8,6,7};
	auto arrSize = sizeof(arr) / sizeof(int);
	int k = 4;
	int kthSmall = getMinKthByBFPRT(arr, arrSize, k);
	printf("%d\n", kthSmall);

	int* lessThanKthArr = getMinKNumsByBFPRT(arr, arrSize, k);
	for (int i = 0; i < k; i++)
	{
		printf("lessThanKthArr[%d]=%d\n", i, lessThanKthArr[i]);
	}

	free(lessThanKthArr);
	return 0;
}